# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre and not tin :
            return None
        tree = TreeNode(pre[0])
        mid = tin.index(pre[0])
        tree.left = self.reConstructBinaryTree(pre[1:mid+1],tin[0:mid])
        tree.right = self.reConstructBinaryTree(pre[mid+1:],tin[mid+1:])
        return tree



# #if not pre and not tin :
#             return None
#         d = {}
#         for i in range(len(tin)):
#             d[tin[i]] = i
#         tree = TreeNode(pre[0])
#         b = tree
#         for i in range(1,len(pre)):
#             if d[pre[i]-1]<d[pre[i]]:
#                 b.right = TreeNode(pre[i])
#                 b = b.right
#             else:
#                 b.left = TreeNode(pre[i])
#                 b=b.left
#         # return tree


pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
s = Solution()
m = s.reConstructBinaryTree(pre,tin)


